package com.example.demo.algorithm.interview;

/**
 * 一个链表,奇数位升序,偶数位降序
 * 请将它整体排成升序
 *
 * @author liweizhi
 * @date 2020/7/7
 */
public class T1SortLinkList {
    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    static void printNode(Node node) {
        Node n = node;
        while (n != null) {
            System.out.print(n.value + " ");
            n = n.next;
        }
        System.out.println("\n---");
    }

    /**
     * 把一个链表,奇数位拆出一个链表,偶数位拆出一个链表
     *
     * @param head
     * @return
     */
    public static Node[] getTwoList(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node head2 = head.next;
        Node cur1 = head;
        Node cur2 = head2;
        Node next;
        while (cur1 != null && cur2 != null) {
            next = cur2.next;
            cur1.next = next;
            cur2.next = next == null ? null : next.next;
            cur1 = next;
            cur2 = cur2.next;
        }
        return new Node[]{head, head2};
    }

    /**
     * 反转单向链表
     *
     * @param node
     * @return
     */
    static Node reverse(Node node) {
        Node pre = null;
        Node next;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    static Node mergeTwoNode(Node node1, Node node2) {
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }
        Node head, cur1, cur2, pre = null, next;
        if (node1.value < node2.value) {
            head = node1;
            cur1 = node1;
            cur2 = node2;
        } else {
            head = node2;
            cur1 = node2;
            cur2 = node1;
        }

        while (cur1 != null & cur2 != null) {
            if (cur1.value <= cur2.value) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        if (cur2 != null) {
            pre.next = cur2;
        }
        return head;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(10);
        node.next.next = new Node(3);
        node.next.next.next = new Node(8);
        node.next.next.next.next = new Node(5);
        node.next.next.next.next.next = new Node(6);
        node.next.next.next.next.next.next = new Node(7);
        Node[] twoList = getTwoList(node);
        Node node1 = twoList[0];
        Node node2 = twoList[1];
        node2 = reverse(node2);

        printNode(node1);
        printNode(node2);
        Node mergeTwoNode = mergeTwoNode(node1, node2);
        printNode(mergeTwoNode);
    }
}
